그리디 알고리즘에 대한 접근
부분 문제의 최적해가 전체 최적해의 일부가 아닐 수 있다 면
그리디(Greedy) 알고리즘으로 접근해서는 안 된다
그리디 알고리즘은 부분의 최적해가 전체의 최적해를 이룬다는 알고리즘이기 때문이다
따라서 지역적으로 최적인 선택이 전체적으로도 최적인 해결책을 만들 수 있어야 함
- 부분 문제의 최적해가 전체 문제의 최적해를 구성하지 않는 경우
- 현재의 선택이 미래의 선택에 부정적인 영향을 줄 수 있는 경우
- 이전의 선택을 나중에 번복해야 할 필요가 있는 경우
라면 그리디 알고리즘에 해당하지 않는다